package Sort;

import java.util.Arrays;

public class QuickSort {
    public static void main(String[] args) {
        int[] data = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
        System.out.println("排序之前：\n" + java.util.Arrays.toString(data));
        quickSort(data, 0, data.length - 1);
        System.out.println("排序之后：\n" + java.util.Arrays.toString(data));

    }

    private static void quickSort(int[] data, int low, int high) {
        int l, h, temp, t;
        if (low > high) {
            return;
        }
        l = low;
        h = high;
        //temp 是基准位  先拿最左边的
        temp = data[low];
        System.out.println("基准位置:" + l + "数字:" + data[low]);
        while (l < h) {
            //先看右边，依次往左递减  右边的 往左走  直到找到小于基数的
            while (temp <= data[h] && l < h) {
                h--;
            }
            //再看左边，依次往右递增  左边的 往右走 直到找到大于基数的
            while (temp >= data[l] && l < h) {
                l++;
            }
            //如果满足条件 交换
            if (l < h) {
                System.out.println("交换：" + data[l] + "和" + data[h]);
                t = data[h];
                data[h] = data[l];
                data[l] = t;
                System.out.println(Arrays.toString(data));
            }
            //最后将基准位与 l和h相等的位置的数字交换
            //最后将基准位与i和j相等位置的数字交换
            System.out.println("基准位" + temp + "和l、h相遇的位置" + data[l] + "交换");
            data[low] = data[l];
            data[l] = temp;
            System.out.println(java.util.Arrays.toString(data));
            //递归调用左半数组
            quickSort(data, low, h - 1);
            //递归调用右半数组
            quickSort(data, h + 1, high);

        }
    }

}
